数字字符串转化成 IP 地址

2023-07-17 17:18| 来源: 网络整理| 查看: 265

数字字符串转化成 IP 地址 1、参考资料

https://www.nowcoder.com/practice/ce73540d47374dbe85b3125f57727e1e

2、题目要求

题目描述

现在有一个只包含数字的字符串，将该字符串转化成IP地址的形式，返回所有可能的情况。

例如：

给出的字符串为"25525511135",

返回["255.255.11.135", "255.255.111.35"](顺序没有关系)

示例

输入

"25525511135"

输出

["255.255.11.135","255.255.111.35"] 3、代码思路

深度优先搜索

这种题其实和迷宫问题类似，我当前搜寻的路径是否能组成有效的 IP 地址，必须要递归到最深层(递归到 IP 地址中最后一段地址)，才能知道是否为有效的 IP 地址每个地址段由 1~3 个数字组成，所以我们需要用个 for 循环来搜索这三种情况：for (int i = startIndex; i < startIndex + 3 && i < str.length(); i++) {，即该地址段可能由 1 个数字组成，也可能是 2 个，也有可能是 3 个那么我们回过头来再想想，递归函数的形参到底需要什么参数呢？源字符串 String str 肯定需要，每一段 IP 地址都需要在源字符串中有个起始索引 int startIndex，还需要有个当前搜索路径记录每段的 IP 地址 List paths，最后的结果(所有合法的 IP 地址)我们使用类变量 ArrayList result 存储我们定义 void restoreIpAddresses(String str, int startIndex, List paths) { 函数，其目的是将数字字符串转换为 IP 地址，二话不说，写递归先写回溯条件：当凑出有效的 IP 地址回溯，即 paths.size() == 4 回溯；或者是当前的 IP 地址不符合要求时开始回溯(不在 0~255 范围之间，这点在写代码的过程中才能想得到)每个 IP 地址段的长度可能为 1~3，所以我们需要搜索这三种可能性，使用 for 循环：if (paths.size() == 4) {，在 for 循环里面有一些细节要处理：如果当前 IP 地址段是最后一段，则直接截取字符串的剩余部分(str.substring(startIndex, str.length()))，做合法性判断之后，直接跳出 for 循环(因为最后一段地址只有一种可能)；否则按照正常处理逻辑，即使用循环变量 i+1 作为 IP 地址段的右边界(str.substring(startIndex, i + 1))由于 List paths 对象属于引用传递，所以整个递归过程中 paths 对象只有一份，我们在进入递归之前，将当前合法的 IP 地址段添加至 paths 中：paths.add(subNum.toString());；然后进入递归：restoreIpAddresses(str, i + 1, paths);；最后恢复现场：paths.remove(paths.size() - 1);。这都是写递归的套路啊，详细可以参考我的博客：组合总和和全排列还有就是之前说的：当前的 IP 地址不符合要求时开始回溯(不在 0~255 范围之间)，因为这种情况下不能搜索出合法的 IP 地址，所以直接回溯至上一层，然后继续搜索 4、代码实现

代码

class Solution { ArrayList result = new ArrayList(); public ArrayList restoreIpAddresses(String str) { restoreIpAddresses(str, 0, new ArrayList()); return result; } private void restoreIpAddresses(String str, int startIndex, List paths) { // 当凑出有效的 IP 地址回溯，即 paths.size() == 4 回溯 if (paths.size() == 4) { result.add(paths.get(0) + "." + paths.get(1) + "." + paths.get(2) + "." + paths.get(3)); return; } // 每个 IP 地址段的长度可能为 1~3，所以我们需要搜索这三种可能性 for (int i = startIndex; i // 将当前合法的 IP 地址段添加至 paths 中 paths.add(subNum.toString()); // 递归搜索 restoreIpAddresses(str, i + 1, paths); // 恢复现场 paths.remove(paths.size() - 1); } else { // 当前的 IP 地址不符合要求时开始回溯(不在 0~255 范围之间) return; } if (paths.size() == 3) { break; } } } }

说明：我不知道牛客网对于 0 的处理是什么方式，反正我就是将字符串 subStr 解析成整形数值 subNum，然后调用 subNum.toString() 去除前导零

【本文地址】

公司简介

联系我们